|
2-3フィンガーツリー〔Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In ''Journal of Functional Programming'' Vol. 16, No. 2, 2006, pp. 197–217, DOI=10.1017/S0956796805005769 http://dx.doi.org/10.1017/S0956796805005769〕(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度つきキューや探索木などを実装できる。 Haskellでは列に特化した実装がData.Sequence としてベースライブラリに含まれる。列に限定しない汎用の実装もfingertreeパッケージ として用意されている。 == 構造 == 2-3フィンガーツリーは分岐数が2または3である木構造に対して「指(finger)」と呼ばれる構造〔Leo J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts, “A new representation for linear lists”, In ''Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77)'', New York, NY, USA: ACM, 1977, pp. 49–60. DOI=10.1145/800105.803395 http://doi.acm.org/10.1145/800105.803395〕を導入して作られる。 通常の平衡木では葉に置いた要素にアクセスする際には根から参照を辿る必要があり、要素数に対して対数時間の計算量が必要となる。しかし多くの場合、頻繁にアクセスする要素は特定の場所やその周辺に偏っている。例えば両端キューの場合、ほとんどの演算は両端やその周辺に対する演算である。そのため毎回根から参照を辿るのは効率が悪い。そこで参照を辿る開始点を変更し、必要に応じてポインタを反転させておき頻繁にアクセスする部分に素早くアクセスできるようにする。この構造を指と言う。以下は完全二分木の両端に対して指を導入した例である(2-3フィンガーツリーではない)。 none まず参照を辿る開始点を両端にする。親からそのノードへの参照を反転させる。そして親から親の親への参照も再帰的に反転させていく。すると両端に近い部分へは素早くアクセスできるようになる。完全二分木の両端に指を導入したものは最初の部分を除いて、2つの完全二分木を要素として持つリストとしても見られる。各完全二分木のサイズは2倍ずつに増えていく。 2-3フィンガーツリーは分岐数が2または3である木構造の両端に指を追加したものであり、分岐数が2または3である木のペアを要素として持つリストとしても見られる。ただしそれらの木の根のみは1から4つの子を持てるように条件を緩和する。これは追加と削除を交互に実行しても処理時間を償却定数時間に保つためである。なお根の分岐数は1から3まででもよい。その場合、計算量のオーダーは変わらないものの木は深くなる。2-3フィンガーツリーをリストとして見た場合、完全二分木に指を導入したときと同じように各要素の木は指数関数的に大きくなる。 2-3フィンガーツリーは形式的には次のように定義される。ここでは記法はHaskellを用いた。 -- 2-3フィンガーツリー data FingerTree a = Empty -- 空の木 | Single a -- 1つだけ要素を持つ木 | Deep (Digit a) (FingerTree (Node a)) (Digit a) -- より深い木 -- 左右の木の根。1から4つの要素を持つ。 data Digit a = One a | Two a a | Three a a a | Four a a a a -- 左右の木の根以外。2つまたは3つの要素を持つ。 data Node a = Node2 a a | Node3 a a a フィンガーツリーは「空の木」「1つだけ要素を持つ木」「深い木」のいずれかである。深い木は列の最初の数要素・最後の数要素・それ以外を保持するフィンガーツリーからなる。Digitは左右の木の根であり、Nodeは分岐数が2または3である平衡木を表す。ただしDigitやNodeは木の深さによって異なる型を持つ。例えばNode Integerは整数を要素としてもつ深さ1の木であり、Node (Node Integer)は整数を要素として持つ深さ2の木である。この型付けは深いフィンガーツリーは左右に持つ木も深くなるという制約を強制し、アルゴリズムを強固で単純にする。左右の木をDigit(数字)と呼んでいるのはフィンガーツリーが数値表現を利用したデータ構造だからである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「2-3 フィンガーツリー」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Finger tree 」があります。 スポンサード リンク
|
